import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : Ding
 * @create 2022/4/15 18:50
 * <p>
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 * <p>
 * 示例 1:
 * <p>
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 * <p>
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 * <p>
 * 输入: s = "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 * 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 * <p>
 * 提示：
 * 0 <= s.length <= 5 * 104
 * s 由英文字母、数字、符号和空格组成
 */
public class _0003_无重复字符的最长子串_中等 {

    public static void main(String[] args) {
        String str = "bfbv";
        int ret = lengthOfLongestSubstring2(str);
        System.err.println(ret);
    }

    /**
     * 推荐：滑动窗口
     * 精简，复杂度低时间也还理想（6ms），可维护和可读性都极高
     * @param str string
     * @return maxLength
     */
    public static int lengthOfLongestSubstring2(String str) {
        //首先创建一个Set无序集合。我们可以利用它的元素唯一性来辅助算法
        Set<Character> tempSet = new HashSet<>();
        //这里我们定义窗口的左右边界，初始值为left = right = 0，即空窗口
        int left = 0,right = 0;
        //定义一个返回值，即最长子串长度，默认0
        int maxLength = 0;
        //当左、右边界均在字符串的长度以内，我们继续
        while(left < str.length() && right < str.length()){
            if (tempSet.contains(str.charAt(right))){
                //如果Set中存在right边界的index所对应的字符时，我们移除左边界的字符
                tempSet.remove(str.charAt(left));
                //同时，左边界右移一个单位
                left ++;
            }else{
                //否则，也就是仍然全为不重复的，我们把新字符插入到Set中
                tempSet.add(str.charAt(right));
                //同时，右边界扩大，右移一个单位
                //tempSet.add(str.charAt(right ++));
                right ++;
            }
            //比较最长
            maxLength = Math.max(maxLength,right - left);
        }
        return maxLength;
    }


    /**
     * 我的解法
     * 能用，但是复杂度较高且很慢（10ms），而且代码的可读性和可维护性极差
     * @param str 字符串
     * @return 最大长度
     */
    public static int lengthOfLongestSubstring1(String str) {
        int maxLength = 0;
        List<String> tempList = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            //遍历字符串，插入到集合中，一旦遇到重复的，就清除集合重复的元素包括之前的内容
            //复杂度类似于On2
            boolean isUnique = true;
            for (int j = 0; j < tempList.size(); j++) {
                if (tempList.get(j).equals(str.substring(i, i + 1))) {
                    //遇到同样的了，把tempList的第j+1之前的素有数据remove掉
                    int k = j + 1;
                    while (k-- > 0) {
                        tempList.remove(0);
                    }
                    //然后在加一个新数据
                    tempList.add(str.substring(i, i + 1));
                    isUnique = false;
                    break;
                }
            }
            if (isUnique) {
                //没有重复的，就插入
                tempList.add(str.substring(i, i + 1));
            }
            //和记录中最长的作比较
            if (maxLength < tempList.size()) {
                maxLength = tempList.size();
            }
        }
        return maxLength;
    }
}